package system2021.src.class18dp;

public class Code02_CardsInLine {

    // 根据规则，返回获胜者的分数
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int first = f1(arr, 0, arr.length - 1);
        int second = g1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }

    // 举例图：![](http://img.yhzcmxq.cn/picgo/8FC2948B694C8D0AB9D7E9806E49A87D.png)
    // arr[L..R]，先手获得的最好分数返回
    public static int f1(int[] arr, int L, int R) {
        // 当前的L和R代表的是当前可以供你选择牌的范围
        if (L == R) {
            // 求A的时候，奇数张牌，这句执行
            // 求B的时候，奇书张牌，这句不执行
            // 偶数张牌，这个结论相反
            return arr[L];
        }
        int p1 = arr[L] + g1(arr, L + 1, R);
        int p2 = arr[R] + g1(arr, L, R - 1);
        return Math.max(p1, p2);
    }

    // // arr[L..R]，后手获得的最好分数返回
    public static int g1(int[] arr, int L, int R) {
        if (L == R) {
            // 求A的时候，奇数张牌，这句不执行
            // 求B的时候，奇书张牌，这句执行
            // 偶数张牌，这个结论相反
            return 0;
        }
        int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
        int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
        return Math.min(p1, p2);
    }

    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int second = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }

    // arr[L..R]，先手获得的最好分数返回
    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (fmap[L][R] != -1) {
            return fmap[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }

    // // arr[L..R]，后手获得的最好分数返回
    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        }
        int ans = 0;
        if (L != R) {
            int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
            int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }

    public static int win3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] f1Dp = new int[N][N];
        int[][] g1Dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            f1Dp[i][i] = arr[i];
        }
        int l;
        int r;
        // 首先要画出图，然后知道遍历的顺序
        // 这里的遍历比较特别：是斜着一条条进行遍历
        for (int startCol = 1; startCol < N; startCol++) {
            l = 0;
            r = startCol;
            while (r < N) {
                g1Dp[l][r] = Math.min(f1Dp[l + 1][r], f1Dp[l][r - 1]);
                f1Dp[l][r] = Math.max(arr[l] + g1Dp[l + 1][r], arr[r] + g1Dp[l][r - 1]);
                l++;
                r++;
            }
        }
        return Math.max(g1Dp[0][N - 1], f1Dp[0][N - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));

    }

}
